package elementaryAlgorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * leetcode 100 相同的树
 * @描述
 * 给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
 *
 * 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
 *
 *  
 *
 * @示例1
 *      1           1
 *     /\          / \
 *   2   3        2   3
 * 输入：p = [1,2,3], q = [1,2,3]
 * 输出：true
 *
 * @示例2
 *      1   1
 *     /    \
 *   2       2
 * 输入：p = [1,2], q = [1,null,2]
 * 输出：false
 *
 * @示例 3
 *      1       1
 *     / \     / \
 *    1   2   2   1
 * 输入：p = [1,2,1], q = [1,1,2]
 * 输出：false
 *  
 *
 * @提示
 *
 * 两棵树上的节点数目都在范围 [0, 100] 内
 * -104 <= Node.val <= 104
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/same-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * */
public class SameTree {
    public static void main(String[] args) {
//        TreeNode node2 = new TreeNode(2);
//        TreeNode node3 = new TreeNode(3);
//        TreeNode p = new TreeNode(1,node2,node3);
//        TreeNode q = new TreeNode(1,node2,node3);
//        SameTree sameTree = new SameTree();

        Integer x = -129;
        Integer y = -129;
        System.out.println(x == y);

       /* TreeNode node2 = new TreeNode(1);
        TreeNode p = new TreeNode(1);
        p.left = node2;
        TreeNode q = new TreeNode(1);
        q.right = node2;
        SameTree sameTree = new SameTree();
        boolean result = sameTree.isSameTree(p, q);
        System.out.println(result);*/

    }
    public boolean isSameTree(TreeNode p, TreeNode q) {
        List<Integer> pre1 = new ArrayList<>();
        List<Integer> mid1 = new ArrayList<>();
        preOrderTrvael(p,pre1);
        midOrderTrvael(p,mid1);

        List<Integer> pre2 = new ArrayList<>();
        List<Integer> mid2 = new ArrayList<>();
        preOrderTrvael(q,pre2);
        midOrderTrvael(q,mid2);

        if (pre1.size() == pre2.size()){
            for (int i = 0; i < pre1.size(); i++) {
                if (pre1.get(i) == null && pre2.get(i) == null){
                    continue;
                }else if ((pre1.get(i) != null && pre2.get(i) == null) || (pre1.get(i) == null && pre2.get(i) != null)){
                    return false;
                }else if (pre1.get(i).intValue() != pre2.get(i).intValue()) {
//                    System.out.println("pre");
                    return false;
                }
            }
        }else {
//            System.out.println("pre.size");
            return false;
        }

        if (mid1.size() == mid2.size()){
            for (int i = 0; i < mid1.size(); i++) {
                if (mid1.get(i) == null && mid2.get(i) == null){
                    continue;
                }else if ((mid1.get(i) != null && mid2.get(i) == null) || (mid1.get(i) == null && mid2.get(i) != null)){
                    return false;
                }else if (mid1.get(i).intValue() != mid2.get(i).intValue()) {
//                    System.out.println("mid");
                    return false;
                }
            }
        }else {
//            System.out.println("mid.size");
            return false;
        }
        return true;
    }

    public void preOrderTrvael(TreeNode root, List result){
        if (root == null){
            result.add(null);
            return;
        }
        result.add(root.val);
        preOrderTrvael(root.left,result);
        preOrderTrvael(root.right,result);
    }

    public void midOrderTrvael(TreeNode root, List result){
        if (root == null){
            result.add(null);
            return;
        }
        preOrderTrvael(root.left,result);
        result.add(root.val);
        preOrderTrvael(root.right,result);
    }
}
